//
// Created by shanshi on 2025/6/9.
//

#ifndef LFU_H
#define LFU_H
#include <memory>
#include <iostream>

/**
 * @file LFU.h
 * @author luxiaolu
 * @brief
 * @version 0.1
 * @date 2025-05-18
 * LFU ：最近最小使用频次
 * 待优化点：
 * 1. 频率爆炸问题： 长期驻留在缓存中的内容，频率计数无限增长，从而导致计数溢出问题
 * 2. 过时热点数据占用缓存： 数据可能后续不再使用，但是由于缓存命中率高，导致数据被保留，从而导致缓存污染
 * 3. 冷启动问题： 刚加入的数据，可能被提前淘汰，从而导致数据丢失
 * 4. 不适合短期数据：
 * 5. 缺乏动态适应性: 固定的LFU策略不能适应不同的应用场景
 * 6. 锁的粒度大，多线程高并发访问下锁的等待时间开销大
 * 不适用场景
 * 锁的粒度大：多线程高并发，同步等待时间开销大 解决方案：将lfu分片
 * 优化：
 * 1. 最大平均访问次数限制
 * 2. hashlfucache
 * @copyright Copyright (c) 2025
 */

template<typename Key, typename Value>
class KLfuCache;

template<typename Key, typename Value>
class FreqList {
private:
 struct Node {
  std::weak_ptr<Node> pre;
  std::shared_ptr<Node> next;
  int freq;
  Key key;
  Value value;

  Node()
   : freq(1), next(nullptr) {
  }

  Node(Key key, Value value)
   : key(key), value(value), freq(1), next(nullptr) {
  }
 };

 using NodePtr = std::shared_ptr<Node>;
 int freq_;
 NodePtr head_;
 NodePtr tail_;

public:
 explicit FreqList(int freq)
  : freq_(freq) {
  head_ = std::make_shared<Node>();
  tail_ = std::make_shared<Node>();
  head_->next = tail_;
  tail_->pre = head_;
 }

 bool isEmpty() {
  return head_->next == tail_;
 }

 void addNode(NodePtr node) {
  // 将node插入到链表尾部
  if (!node || !head_ || !tail_) {
   std::cout << "Error: node or head_ or tail_ is NULL!\n" << std::endl;
   return;
  }
  node->pre = tail_->pre;
  node->pre.lock()->next = node;
  node->next = tail_;
  tail_->pre = node;
 }

 void removeNode(NodePtr node) {
  if (!node || !head_ || !tail_) {
   std::cout << "Error: node or head_ or tail_ is NULL!\n" << std::endl;
   return;
  }
  if (node->pre.expired() || !node->next) {
   return;
  }
  // 将node从链表中删除
  node->pre.lock()->next = node->next;
  node->next->pre = node->pre.lock();
  node->next = nullptr; // 显示设置为null，彻底断开链接
 }

 NodePtr getFirstNode() const {
  return head_->next;
 }

 friend class KLfuCache<Key, Value>;
};


#endif //LFU_H
